For the design of digital circuits on the scale of VLSI (Very Large Scale Integration) technology, designers often employ computer-aided techniques. Standard languages known as Hardware Description Languages (HDL's) have been developed to describe digital circuits to aid in the design and simulation of complex digital circuits. Several hardware description languages, such as VHDL and Verilog, have evolved as industry standards. VHDL and Verilog are general purpose hardware description languages which allow definition of a hardware model at the gate level, the register transfer level (RTL), or the behavioral level using abstract data types. As device technology continues to advance, various product design tools have been developed to adapt HDLs for use with newer devices and design styles.
One important aspect in the field of circuit synthesis and simulation is in the modeling and analysis of finite state machines. A state machine is a generalized type of sequential logic in which the next state of the machine (or circuit) can be written as a function of the current state and the value of the input signals to the machine. Because state machines can be used to represent digital circuits which combine combinational logic and a memory element, state machines are a fundamental building block in the synthesis of large scale digital circuits. The modeling of state machines is especially important given the prevalent use of programmable logic devices to implement sequential logic functions within a circuit. It is desirable to identify a state machine within a logic design because well known optimizations can be performed on the state machine. Further, a state machine may be debugged by using conventional debugging methods. However, designers who use HDL to create circuit designs often do not intentionally include a state machine in a circuit design. That is, a designer may merely write HDL code specifying the circuit design without intending to include a state machine and without realizing that, in fact, a state machine has been unintentionally included in the circuit design. Thus, the optimization and debugging of state machines is not possible when a state machine is included in this manner because the state machine's existence in the design is unrecognized and its definition in a symbolic form (e.g. definition by a next state function or by a state diagram or state table) is not provided by the designer or as a result of a compiler's logic synthesis.
Present methods and products associated with HDL synthesis accommodate the analysis of finite state machines (FSM). These methods, however, require the users to either constrain the style in which the finite state machine is described by following a rigid coding template, or to isolate the finite state machine from other parts of the design and identify the HDL variable representing the current state of the finite state machine. In the first case the restriction allows the finite state machine to be recognized with pattern matching on the original HDL source code. In the second, the state machine is extracted from a netlist with Boolean logic techniques, relying on the user's identification of both the state register and the portion of the design that is to be considered part of the state machine.
The identification of the part of the design and design information that is involved in the state machine is important. Not including enough of the design will lead to an extracted state machine that contains many states that are not reachable (invalid) in the whole design as well as state to state transitions that cannot be activated within the context of the whole design. These invalid states and transitions will both create a larger optimization problem as well as biasing the finite state machine optimization towards getting a good result for states and transitions which are not needed. Including too much of the design yields an analysis problem that can be computationally difficult or impractical, as well as disturbing the optimization of parts of the design that did not need to be included.
One deficiency in these techniques is that only circuits that the user thinks of as state machines and that the user makes the effort to identify are treated as state machines.
A second deficiency is that theses techniques place strong constraints on the way the user can describe state machines, either by requiring a rigid coding template to be followed or by requiring he design to be organized to isolate the state machine (for example, using design hierarchy) from other parts of the design.
It is therefore desirable to provide a system which automatically identifies finite state machines in a circuit.
It is further desirable to provide a system that determines what part of the design should be included in the state machine extraction process.
It is further desirable to provide a system for automatically extracting identified state machines and representing the state machines in symbolic or functional form to facilitate further analysis and optimization.